We introduce the TANAMI program (Tracking Active Galactic Nuclei with Austral Milliarcsecond Interferometry) which is monitoring an initial sample of 43 extragalactic jets located south of -30 degrees declination at 8.4 GHz and 22 GHz since 2007. All aspects of the program are discussed. First epoch results at 8.4 GHz are presented along with physical parameters derived therefrom. We present first epoch images for 43 sources, some observed for the first time at milliarcsecond resolution. Parameters of these images as well as physical parameters derived from them are also presented and discussed. These and subsequent images from the TANAMI survey are available at http://pulsar.sternwarte.uni-erlangen.de/tanami/ We obtain reliable, high dynamic range images of the southern hemisphere AGN. All the quasars and BL Lac objects in the sample have a single-sided radio morphology. Galaxies are either double-sided, single-sided or irregular. About 28% of the TANAMI sample has been detected by LAT during its first three months of operations. Initial analysis suggests that when galaxies are excluded, sources detected by LAT have larger opening angles than those not detected by LAT. Brightness temperatures of LAT detections and non-detections seem to have similar distributions. The redshift distributions of the TANAMI sample and sub-samples are similar to those seen for the bright gamma-ray AGN seen by LAT and EGRET but none of the sources with a redshift above 1.8 have been detected by LAT.